//插入、删除和随机访问都是 O(1) 的容器
class RandomizedSet {
public:
    /** Initialize your data structure here. */

    //插入和删除 O(1) 用哈希表就可以解决
    //问题在于不能支持随机访问
    //所以还需要搭配vector进行使用
    RandomizedSet() 
    {
        srand(time(0));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) 
    {
        if(_hash.find(val)==_hash.end())
        {
            //不存在
           _v.push_back(val);
           _hash[val]=_v.size()-1;
            return true;
        }
        else
        {
            return false;
        }

    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) 
    {
        if (_hash.find(val) == _hash.end()) 
        {
            return false;
        }
        //用最后一个 _index位置的值去覆盖删除的值
        int index=_v.size()-1;
        _v[_hash[val]]=_v[index];
        _hash[_v[index]]=_hash[val];
        _hash.erase(val);
        _v.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() 
    {
        int randindex= rand()%_v.size();
        return _v[randindex];
    }
private:
    vector<int>_v;
    unordered_map<int,int> _hash;// -> 数值 在数组中的下标
    //int _index=0;//到哪个下标处了
};

//重排链表
class Solution {
public:
    void reorderList(ListNode* head) 
    {
        //把节点全部放入链表，一次取前面的一次取后面的
        vector<ListNode*>v;
        if(head==nullptr) return;
        ListNode* cur=head;
        while(cur)
        {
            v.push_back(cur);
            cur=cur->next;
        }
        cur=head;
        int count=1;
        //一开始--count=0时，从前面取的，所以约定
        //i为偶数次 从前面取 ， i为奇数次 从后面取
        int i=1;int j=v.size()-1;
        while(i<=j)
        {
            if(count%2==1)
            {
                cur->next=v[j];
                j--;
                cur=cur->next;
            }
            else
            {
                cur->next=v[i];
                i++;
                cur=cur->next;
            }
            count++;
        }
        cur->next=nullptr;
    }
};

//回文链表
class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        vector<int>v;
        ListNode* cur=head;
        while(cur)
        {
            v.push_back(cur->val);
            cur=cur->next;
        }
        int i=0,j=v.size()-1;
        while(i<j)
        {
            if(v[i]!=v[j]) return false;
            i++;
            j--;
        }
        return true;
    }
};


//展开多级双向链表
class Solution {
public:
    //优先向下探索,用栈保存上层节点用于回溯
    Node* flatten(Node* head) 
    {
        if (!head) return head;
        stack<Node*>st;
        Node* front=head;
        st.push(front->next);
        if(front->child)
        {
            st.push(front->child);
        }
        while(!st.empty())
        {
            Node*cur=st.top();
            //此时cur是头结点的child节点 或者 头结点的next节点
            //但不管是哪个 我们都需要处理它 所以无所谓
            //当前节点有child走child的 但要记录当前节点的next
            //使得 当前节点的child走回来之后 可以让它的next指针指向next结点
            st.pop();
            //因为我们要优先遍历child节点
            //看看cur有没有child节点 
            while(cur)
            {
                front->next=cur;
                cur->prev=front;
                front->child=nullptr;
                front=cur;
                if(cur->child)
                {
                    st.push(cur->next);
                    cur=cur->child;
                }
                else
                {
                    cur=cur->next;
                }
            }
        }
        return head;
    }
};


//排序的循环链表


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    //题意就是 这是一个循环的 非递减双向链表 
    //只是这个head 不一定是头结点
    Node* insert(Node* head, int insertVal) 
    {
        Node* newnode=new Node(insertVal);
        if(head==nullptr)
        {
            newnode->next=newnode;
            return newnode;
        }
        if(head->next==head)
        {
            head->next=newnode;
            newnode->next=head;
            return head;
        }
        Node* cur=head;
        Node* after=head->next;

      
        // while(after!=head)
        // {
        //     if(cur->val <= insertVal && after->val >=insertVal)
        //     {
        //         cur->next=newnode;
        //         newnode->next=after;
        //     }
        //     else if( cur->val >= after->val) 注意这个=
        //     {
        //         if(insertVal > cur->val || insertVal < after->val )
        //         {
        //             cur->next=newnode;
        //             newnode->next=after;
        //         }
        //     }
        // }
        //这样写 会导致 3 4 1 插入2时 由于 after走到了head 导致没有插入进去
        while(after!=head)
        {
            if(cur->val <= insertVal && after->val >=insertVal)
            {
                break;
            }
            else if( cur->val > after->val)
            {
                if(insertVal > cur->val || insertVal < after->val )
                {
                    break;
                }
            }
            cur=cur->next;
            after=after->next;
        }
        cur->next=newnode;
        newnode->next=after;
        return head;
    }
};
